'''
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

数组中两个数相加，得到目标。

求解：
在有序状态下，从后向前是逐渐缩小，从前向后逐渐增大。
[-4, -1, 0, 1, 2]
 0             4

当 start + end < target 时，end已经不能在增大了，只能增大start。
当 start + end > target 时，start不能在缩小了，只能缩小end。

一直到找到 target 或 start 与 end 相遇结束。
'''

def twoSum(nums, target):
    mapDict = {}
    for index,num in enumerate(nums):   # 列表映射成字典
        # print(mapDict)
        if (target - num) in mapDict:
            return [mapDict[target - num],index]
        mapDict[num] = index
    return None

# start和end的问题在于要将原来数字的下标记住
def twoSum1(nums,target):
    num_id = sorted(range(len(nums)),key= lambda x:nums[x])
    start = 0
    end = len(nums) - 1
    while start < end:
        sum = nums[num_id[start]] + nums[num_id[end]]
        if sum == target:
            return [num_id[start],num_id[end]]
        elif sum < target:
            start = start + 1
        else:
            end = end - 1
    return None


if __name__ == '__main__':
    # print(twoSum([1,3,5,6],4))
    print(twoSum1([3, 2, 4], 6))